P2257 YY的GCD

显然，题目求的是：

$\sum_{p\in prime}\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=p]$

$\sum_{p \in prime}\sum_{i=1}^{ \lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{p} \rfloor}[gcd(i,j)=1]$

有一个与莫比乌斯函数有关的性质：$\sum_{d | n}\mu(d)=[n=1]$

$\sum_{p \in prime}\sum_{i=1}^{ \lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{p} \rfloor}\sum_{k|gcd(i,j)}\mu(k)$

将 $k$ 往前移，然后是一个非常经典的式子了

$\sum_{p \in prime}\sum_{k=1}^{min(\lfloor \frac{n}{p} \rfloor,\lfloor \frac{m}{p} \rfloor)}\mu(k)\lfloor \frac{n}{kp} \rfloor \lfloor \frac{m}{kp} \rfloor$

令$T=kp$,将它放到前面枚举：

$\sum_{T=1}^{min(n,m)}\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor\sum_{p|T,p \in prime} \mu(\frac{T}{p})$

前面的可以用数轮分块解决，后面的可以将每个数对它的倍数的贡献计算，最后做一遍前缀和也可以分块了。

#include <cstdio>
#include <iostream>
using namespace std;

const int MAXN = 10000000;
int t , a , b , d;

int k , prime[ MAXN + 5 ] , mu[ MAXN + 5 ];
long long f[ MAXN + 5 ];
bool vis[ MAXN + 5 ];

void sieve( ) {
	mu[ 1 ] = 1;
	for( int i = 2 ; i <= MAXN ; i ++ ) {
		if( !vis[ i ] ) {
			prime[ ++ k ] = i;
			mu[ i ] = -1;
		}
		for( int j = 1 ; j <= k && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
			vis[ i * prime[ j ] ] = 1;
			if( i % prime[ j ] == 0 ) break;
            mu[ i * prime[ j ] ] = -mu[ i ];
            
		}
	}
}
void Init( ) {
    sieve( );
    for( int j = 1 ; j <= k ; j ++ )
       for( int i = 1 ; 1ll * i * prime[ j ] <= MAXN ; i ++ )
               f[ i * prime[ j ] ] += mu[ i ];
    for( int i = 2 ; i <= MAXN ; i ++ )
        f[ i ] += f[ i - 1 ];
}

long long solve( int n , int m ) {
    long long Ans = 0;
    for( int l = 1 , r ; l <= min( n , m ) ; l = r + 1 ) {
        r = min( n / ( n / l ) , m / ( m / l ) );
        Ans += 1ll * ( n / l ) * ( m / l ) *  ( f[ r ] - f[ l - 1 ] );
    }
    return Ans;
}

int main( ) {
	Init( );
	scanf("%d",&t);
	while( t -- ) {
		scanf("%d %d",&a,&b);
		printf("%lld\n",solve( a , b ));
	}
	return 0;
}